package com.剑指offer.第三章;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入字符串s1 和 s2 如何判断字符串s2中是否包含字符串s1的某个变位词？如果字符串s2中包含字符串s1的某个变位词，则字符串s1至少有一个变位词是字符串s2的子字符串。
 * 假设：字符串s1为"ac"，字符串s2为"dgcaf"，由于字符串s2中包含字符串s1的变位词"ca"，因此输出true
 */
public class 字符串中的变位词 {

    /**
     * 用数组记录s1中每个字母出现的次数
     *
     * @param s1 ca
     * @param s2 dgcaf
     * @return 当存在变位词时，就返回true
     */
    public static boolean resolve(String s1, String s2) {
        int[] counts = new int[26];
        /**
         * 首页记录s1中字符出现的次数
         */
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }

        if (isZero(counts)) {
            return true;
        }

        // 使用双指针 表示子字符串，长度为s1的长度。
        // 指针向右移动 最右边添加一个字符 最左边删除一个字符 每当在子字符串中添加一个字符时，就在数组中对应的位置-1，每当删除一个字符串就在对应的位置+1
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++;
            if (isZero(counts)) {
                return true;
            }
        }
        return false;

    }

    /**
     * @param s1
     * @param s2
     * @return
     */
    public static List<Integer> resolve1(String s1, String s2) {
        ArrayList<Integer> indices = new ArrayList<>();
        int[] counts = new int[26];
        /**
         * 首页记录s1中字符出现的次数
         */
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
            counts[s2.charAt(i) - 'a']--;
        }

        if (isZero(counts)) {
            indices.add(0);
        }

        // 使用双指针 表示子字符串，长度为s1的长度。
        // 指针向右移动 最右边添加一个字符 最左边删除一个字符 每当在子字符串中添加一个字符时，就在数组中对应的位置-1，每当删除一个字符串就在对应的位置+1
        for (int i = s1.length(); i < s2.length(); i++) {
            counts[s2.charAt(i) - 'a']--;
            counts[s2.charAt(i - s1.length()) - 'a']++;
            if (isZero(counts)) {
                indices.add(i - s1.length() + 1);
            }
        }
        return indices;
    }


    public static boolean isZero(int[] counts) {
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        List<Integer> list = resolve1("acb", "cbcadf");
        for (Integer integer : list) {
            System.out.println(integer);
        }
    }

}
